package com.imooc.distributedemo.leetcode;

/**
 * 最长回文字符串  动态规划
 */
public class LongestPalindrome {

//    public static int longestPalindromeSubseq(String s) {
//        int len = s.length();
//        int[][] dp = new int[len][len];
//        //初始化
//        for(int i = 0; i < len; i++) {
//            dp[i][i] = 1;
//        }
//        //递推
//        for(int i = len - 1; i >= 0; i--) {
//            for(int j = i + 1; j < len; j++) {
//                if(s.charAt(i) == s.charAt(j)) {
//                    dp[i][j] = dp[i + 1][j - 1] + 2;//两端的元素都考虑
//                } else {
//                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);//两端元素只考虑最大的
//                }
//            }
//        }
//        return dp[0][len - 1];
//    }

//    public static String longestPalindrome(String s) {
//        int len = s.length();
//        if(s.length() < 2) return s;//特殊处理
//
//        //查找最长字符串
//        int maxlen  = 0;
//        int begin = 0;
//        char stoc[] = s.toCharArray();
//        boolean dp[][] = new boolean [len][len];
//        //for(int i = 0; i < len; i ++) dp[i][i] = true;//初始化
//
//        for(int j = 0; j < len; j ++)//填表格
//            for(int i = 0; i <= j; i ++) {//从上往下填
//
//                if(stoc[i] != stoc[j]) {//两头不一样，那就不是回文
//                    dp[i][j] = false;
//                }
//                else {
//                    if(j - i < 3) dp[i][j] = true;//如果内部字符串长度小于2则为回文
//                    else {
//                        dp[i][j] = dp[i + 1][j - 1];//否则迭代
//                    }
//                }
//
//                if(dp[i][j] == true && j - i + 1 >= maxlen) {//查找
//                    maxlen = j - i + 1;
//                    begin = i;
//                }
//
//            }
//
//        return s.substring(begin, begin + maxlen);//左闭右开
//    }

    public static boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            boolean valEqual = s.charAt(i) != s.charAt(len - i - 1);
            if (valEqual) {
                return false;
            }
        }
        return true;
    }

    // 暴力解法
    public static String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        return ans;
    }

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
//        输入：s = "babad"
//        输出："bab"
//        解释："aba" 同样是符合题意的答案
        String str1 = "babad";
        String result1 = longestPalindrome(str1);
        System.out.println(result1);

//        输入：s = "cbbd"
//        输出："bb"
        /*String str2 = "cbbd";
        String result2 = longestPalindrome(str2);
        System.out.println(result2);*/
    }
}
